package com.imooc.distributedemo.rithm;


public class LinkedList {

    /**
     * 头节点
     */
    private Node head;

    /**
     * 尾节点
     */
    private Node tail;

    /**
     * 链表是否为空
     */
    private boolean isEmpty;

    public LinkedList() {
        this.isEmpty = true;
    }

    /**
     * 向单链表中插入数据
     * @param data
     */
    public void insert(int data){
        Node newNode = new Node(data, null);
        if(this.isEmpty){
            head = newNode;
        }else {
            tail.next = newNode;
        }
        tail = newNode;
        this.isEmpty = false;
    }

    /**
     * 单链表的遍历
     */
    public void traversal(){
        if(this.isEmpty){
            return;
        }
        Node current = head;
        while (current != null){
            System.out.println(current.data);
            current = current.next;
        }
    }

    /**
     * 节点类
     */
    private class Node{
        private int data;

        private Node next;

        public Node(int data, Node next) {
            this.data = data;
            this.next = next;
        }

        public int getData() {
            return data;
        }

        public Node setData(int data) {
            this.data = data;
            return this;
        }

        public Node getNext() {
            return next;
        }

        public Node setNext(Node next) {
            this.next = next;
            return this;
        }
    }

    public void reverse(){
        if(head == tail){
            return;
        }

        Node prev = head;
        Node pcur = prev.next;

        while (pcur!=null){
            prev.next = pcur.next;
            System.out.println(prev);
            System.out.println(pcur);
            pcur.next = head;
            System.out.println("============");
            System.out.println(prev);
            System.out.println(pcur);
            head = pcur;
            pcur = prev.next;
        }
        tail = prev;
    }

    public static void iteratorReverse(LinkedList list){

    }

    public  void recurseReverse(){
        if(head == null){
            return;
        }
        // 前一个节点
        Node p = head;
        // 当前节点
        Node q = head.next;
        // 存储下一个节点
        Node temp;
        // 当q为null  则最终p变成尾部指针
        while(q!=null){
            temp = q.next;
            // 改变当前指针的指向，从指向next变成指向pre
            q.next = p;
            // 移动当前指针和下一个指针
            p = q;
            q = temp;
        }
        // 此时p是最后一个节点 也是新的头节点
        head = p;
    }


    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
        linkedList.insert(1);
        linkedList.insert(2);
        linkedList.insert(3);
        linkedList.insert(4);
        linkedList.insert(5);
        linkedList.traversal();
        System.out.println("=====翻转之后=======");
        // linkedList.reverse();
        linkedList.recurseReverse();
        linkedList.traversal();
    }
}
